#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct Trie {
    bool val;
    struct Trie* next[26];
} Trie;


Trie* trieCreate() {
    Trie* newnode = (Trie*)malloc(sizeof(Trie));
    newnode->val = false;
    for (int i = 0; i < 26; i++)
    {
        newnode->next[i] = NULL;
    }
    return newnode;
}

void trieInsert(Trie* obj, char* word) {
    for (int i = 0; word[i] != '\0'; i++)
    {
        if (obj->next[word[i] - 'a'] == NULL)
        {
            obj->next[word[i] - 'a'] = trieCreate();
        }
        obj = obj->next[word[i] - 'a'];
    }
    obj->val = true;
}

bool trieSearch(Trie* obj, char* word) {
    for (int i = 0; word[i] != '\0'; i++)
    {
        if (obj->next[word[i] - 'a'] == NULL)
        {
            return false;
        }
        obj = obj->next[word[i] - 'a'];
    }
    return obj->val;
}

bool trieStartsWith(Trie* obj, char* prefix) {
    for (int i = 0; prefix[i] != '\0'; i++)
    {
        if (obj->next[prefix[i] - 'a'] == NULL)
        {
            return false;
        }
        obj = obj->next[prefix[i] - 'a'];
    }
    return true;
}

void trieFree(Trie* obj) {
    for (int i = 0; i < 26; i++)
    {
        if (obj->next[i])
        {
            trieFree(obj->next[i]);
        }
    }
    free(obj);
}